27.0 KB · ⇊ 8 parts · ⤓ Micron 27.0 KB · ⤓ HTML 50.0 KB

top

Lo mwdamwdqscheduler (in italiano mwdgpianificatore o mwdwgestore dei processi), in mweainformatica, è un componente di un mweqsistema operativo ovvero un mwegprogramma che implementa un mwewalgoritmo di mwfascheduling (in italiano algoritmo di pianificazione) il quale, dato un insieme di richieste di accesso ad una mwfqrisorsa (tipicamente l'accesso al mwfgprocessore da parte di un mwfwprocesso da mwgaeseguire), stabilisce un ordinamento temporale per l'mwgqesecuzione di tali richieste, privilegiando quelle che rispettano determinati parametri secondo una certa politica di mwggscheduling, in modo da ottimizzare l'accesso a tale risorsa e consentire così l'espletamento del servizio/istruzione o processo desiderato.

L'attenzione posta su alcuni parametri piuttosto che su altri differenzia la cosiddetta politica di scheduling all'interno della gestione dei processi dando vita a mwhacode di priorità: ad esempio lo scheduler può eseguire le richieste in base al loro ordine di arrivo (mwhqFIFO), oppure dare precedenza a quelle che impegnano per meno tempo la risorsa (mwhgSNPF); possono esistere politiche che si basano su principi statistici o sulla predizione per individuare un ordinamento delle richieste che si avvicini il più possibile a quello ottimale.

• Descrizione

• Scheduler a breve termine del processore ( dispatcher )

• Scheduling della CPU

• Modello a macchina singola (modello di Karg e Thompson)

• FCFS

• RR

• SJF

• Retroazione multilivello

• FSS

• Scheduling nelle reti

• Bibliografia

• Voci correlate

• Altri progetti

• Collegamenti esterni

Generalmente l'obiettivo dello mwigscheduling è quello di:

• massimizzare il mwjqmwjgthroughput, ovvero la produttività dell'intero sistema, minimizzando i tempi in cui la risorsa è inutilizzata;

• cercare l'ordinamento di richieste che minimizza il rapporto tra tempo di servizio (ovvero il tempo che una richiesta impiega per essere soddisfatta) e tempo di "turnaround" (il lasso di tempo che intercorre tra l'istante in cui la richiesta è generata e quello in cui la richiesta è soddisfatta);

• evitare fenomeni indesiderati come la mwkqmwkgstarvation ovvero "l'attesa eterna" di alcune richieste, verificabile in determinate condizioni;

• dare all'utente del sistema la percezione che le richieste vengano soddisfatte contemporaneamente.

Esistono in realtà molti requisiti che possono essere presi in considerazione, dipendenti anche dal problema specifico che lo mwlqscheduler deve gestire: esistono scheduler che si occupano di suddividere il tempo di uso del processore da parte di un processo, mwlgscheduler che gestiscono richieste di lettura/scrittura da una periferica, anche gli mwlwalgoritmi di sostituzione delle pagine della memoria sono da considerarsi mwmascheduler.

È un componente fondamentale dei mwnqsistemi operativi mwngmultiprocesso, e sicuramente l'esempio più diffuso e critico di mwnwscheduler. È in grado di far eseguire, al mwoaprocessore di un mwoqcomputer, attraverso l'omonima operazione di scheduling, più mwogprocessi (mwowtask) concorrentemente attraverso varie politiche di scheduling. Esso rappresenta dunque il gestore del multitasking attraverso criteri di assegnazione delle risorse di memorizzazione/elaborazione ai vari processi, implementati a loro volta attraverso vari tipi di algoritmi di scheduling.

Generalmente infatti mwpqcomputer con un mwpgprocessore sono in grado di eseguire un processo per volta, quindi per poter far convivere più task è necessario usare uno mwpwscheduler. Nel dettaglio lo scheduler si occupa di far avanzare un processo interrompendone temporaneamente un altro, realizzando così una mwqacommutazione di contesto all'interno del mwqqciclo del processore. Esistono vari mwqgalgoritmi di mwqwscheduling che permettono di scegliere nella maniera più efficiente possibile quale task far proseguire: ad esempio il mwrakernel mwrqlinux nella versione 2.4 ha uno scheduler mwrgO(n), mentre dalla versione 2.6 ha un algoritmo di complessità mwrwO(1), ossia in grado di determinare in un tempo costante quale processo debba essere eseguito, indipendentemente dal numero di processi in attesa.

Ci sono vari modelli di schedulazione:

• Modello a macchina singola.

• Flow-shop (modello di Johnson).

• Algoritmo euristico di Campbell, Dudek e Smith.

• mwtgJob-shop.

Lo scheduling è un'operazione molto importante per il corretto ed efficiente funzionamento del calcolatore. Infatti non solo consente di eseguire più programmi concorrentemente, ma consente anche di migliorare l'utilizzo del processore. Ad esempio, quando è necessario eseguire un'operazione di I/O, il processore non può proseguire l'elaborazione del processo attualmente in esecuzione fino al completamento della stessa. Dato che le operazioni di I/O sono molto più lente del processore sarebbe un inutile spreco di risorse se il processore rimanesse bloccato fino al completamento delle stesse. Per evitare questo le operazioni di I/O vengono gestite unicamente dal mwvaSistema operativo che, nel frattempo, assegna l'uso del processore ad un altro processo. In questo modo si massimizza l'uso delle risorse del sistema.

È importante la distinzione tra scheduling con diritto di mwvgprelazione (scheduling mwvwpreemptive) e scheduling senza diritto di prelazione (scheduling mwwanon-preemptive o mwwqcooperative). Nel primo caso lo scheduler può sottrarre il possesso del processore al processo anche quando questo potrebbe proseguire nella propria esecuzione. Nel secondo caso, invece, lo scheduler deve attendere che il processo termini o che cambi il suo stato da quello di esecuzione a quello di attesa.

Esistono vari algoritmi di scheduling che tengono conto di varie esigenze e che possono essere più indicati in alcuni contesti piuttosto che in altri. La scelta dell'algoritmo da usare dipende da cinque principali criteri:

• Utilizzo del processore: la mwxqCPU (ovvero il processore) deve essere attiva il più possibile, ovvero devono essere ridotti al minimo i possibili tempi morti.

• Throughput: il numero di processi completati in una determinata quantità di tempo.

• Tempo di completamento: il tempo che intercorre tra la sottomissione di un processo ed il completamento della sua esecuzione.

• Tempo d'attesa: il tempo in cui un processo pronto per l'esecuzione rimane in attesa della CPU (waiting time).

• Tempo di risposta: il tempo che trascorre tra la sottomissione del processo e l'ottenimento della prima risposta.

Per analizzare gli algoritmi che verranno successivamente presentati verrà utilizzato il criterio del tempo d'attesa medio dei processi presi in considerazione.

Un algoritmo di scheduling si pone i seguenti obiettivi:

• mwaaFairness (equità): processi dello stesso tipo devono avere trattamenti simili

• mwagBalance (bilanciamento): tutte le parti del sistema devono essere sfruttate

Inoltre bisogna effettuare un distinguo tra i mwbasistemi batch e i mwbqsistemi interattivi. Nei primi il mwbgthroughput deve essere massimizzato e il mwbwTempo di Turnaround deve essere minimizzato. Nei secondi, i sistemi interattivi, il tempo di risposta deve essere il minimo possibile per dare l'idea di continuità all'utente e la proporzionalità deve essere rispettata, ossia il tempo di risposta deve essere proporzionale alla complessità dell'azione.

Passi dell'algoritmo:

1. Selezionare casualmente due mwdajob.

2. Selezionare un nuovo mwdgjob e provare a disporlo nella sequenza corrente.

3. Per ogni posizione provata calcolare il mweaset-up complessivo.

4. Allocare il mwegjob nella posizione che garantisce i più bassi tempi di mwewset-up.

5. Se vi sono ancora mwfqjob da allocare vai al passo 2, altrimenti termina.

L'algoritmo FCFS (mwgaFirst come, first served) è un tipo di algoritmo mwgqFIFO: esegue i processi nello stesso ordine in cui essi vengono sottomessi al sistema. Il primo processo ad essere eseguito è esattamente quello che per primo richiede l'uso della CPU. Quelli successivi vengono serviti non appena questo ha terminato la propria esecuzione, e così avviene successivamente per tutti gli altri posti in coda. Questo tipo di algoritmo è molto semplice da implementare ma solitamente è anche poco efficiente, almeno considerando il tempo medio d'attesa.

Infatti, prendiamo ad esempio la sottomissione nell'ordine dei seguenti processi con la seguente durata espressa in millisecondi:

• p1: 10

• p2: 4

• p3: 2

Verranno eseguiti nello stesso ordine: p1 → p2 → p3

Il processo p1 non attende nulla, perché entra immediatamente in esecuzione. Il processo p2 attende 10 millisecondi, e p3 14. Il tempo medio d'attesa quindi è (0+10+14)/3=8 millisecondi. Si ha allora un effetto convoglio, caratterizzato dal fatto che più processi brevi attendono la terminazione di un unico processo più corposo. Un risultato decisamente diverso da quello ottenibile, in forma teorica, dall'algoritmo ottimale SJF (Shortest Job First) pari a (0+2+6)/3=8/3 millisecondi solamente.

Tuttavia se i processi sono mwigCPU-bound e lunghi, il mwiwFCFS rimane l'algoritmo migliore.

L'algoritmo di scheduling RR (mwkaround-robin) è un particolare algoritmo con prelazione (preemptive) che esegue i processi nell'ordine d'arrivo, come il FCFS, ma esegue la prelazione del processo in esecuzione, ponendolo alla fine della coda dei processi in attesa, qualora l'esecuzione duri più della "quantità di tempo" stabilita, e facendo proseguire l'esecuzione al successivo processo in attesa.

Ad esempio nell'ipotesi che vi siano i seguenti processi in coda con relativa durata in millisecondi, e la quantità di tempo stabilita di 20 ms:

• p1: 30

• p2: 15

• p3: 60

• p4: 45

Verranno eseguiti nel seguente ordine:

• p1 (interrotto dopo 20 ms, ne rimangono altri 10)

• p2 (termina la propria esecuzione perché dura meno di 20 ms)

• p3 (interrotto dopo 20 ms, ne rimangono altri 40)

• p4 (interrotto dopo 20 ms, ne rimangono altri 25)

• p1 (termina la propria esecuzione perché necessitava di meno di 20 ms)

• p3 (interrotto dopo 20 ms, ne rimangono altri 20)

• p4 (interrotto dopo 20 ms, ne rimangono altri 5)

• p3 (termina la propria esecuzione perché necessitava di esattamente 20 ms)

• p4 (termina la propria esecuzione)

Le prestazioni di quest'algoritmo sono dunque influenzate dal tempo medio d'attesa, sebbene consenta a tutti i processi di ottenere il controllo della CPU ed evita quindi il problema dell'attesa indefinita (mwowstarvation).

È inoltre da tenere in considerazione l'impatto dovuto ai frequenti mwpqcontext switch effettuati. È necessario quindi calcolare correttamente la durata ottimale della quantità di tempo per far sì che l'incidenza dei cambi di contesto sia abbastanza limitata, come anche i tempi di attesa. Si può stabilire che, per un funzionamento ottimale, le sequenze di operazioni di CPU dovrebbero essere più brevi della quantità di tempo stabilita in circa l'80% dei casi.

Interessante in questo caso il discorso della media, in quanto risulta molto più stabile di come appare nelle altre strategie. In questo caso, la media va calcolata sommando le 4 differenze tra istante finale di esecuzione del processo e relativo burst. Andando quindi a rappresentare graficamente l'andamento dei processi da p1 a p4, notiamo che p1 termina all'istante 85, p2 all'istante 35, p3 all'istante 145, p4 all'istante 150. Sommando le differenze avremo [(85-30)+(35-15)+(145-60)+(150-45)]/4. La media risultante è 66,25 ms (Tempo di attesa).

Gli algoritmi SJF (mwqwmwrashortest job first), possono essere sia non-preemptive (SNPF) sia preemptive (SRTF).

Non potendo conoscere il tempo per il quale il job occuperà il processore (per il mwrgproblema della fermata), il sistema operativo utilizzerà i dati di precedenti elaborazioni. Per far ciò viene usata la formula:

mwsq τ τ n + 1 = α α t n + ( 1 − − α α ) τ τ n {\displaystyle \tau _{n+1}=\alpha t_{n}+(1-\alpha )\tau _{n}}

Dove (0<=α<=1).

In particolare:

• mwtg α α = 0 ⇒ ⇒ τ τ n + 1 = τ τ n {\displaystyle \alpha =0\Rightarrow \tau _{n+1}=\tau _{n}} (la storia recente non viene considerata)

• mwua α α = 1 ⇒ ⇒ τ τ n + 1 = t n {\displaystyle \alpha =1\Rightarrow \tau _{n+1}=t_{n}} (conta solo l'ultimo valore reale del CPU burst)

L'algoritmo SNPF (mwuwShortest Next Process First) prevede che venga eseguito sempre il processo con il tempo di esecuzione più breve tra quelli in attesa. Prendiamo ad esempio che siano stati sottomessi contemporaneamente i seguenti processi, con la rispettiva durata di esecuzione in millisecondi:

• p1: 10

• p2: 2

• p3: 6

• p4: 4

I processi vengono eseguiti nel seguente ordine: p2 → p4 → p3 → p1

Non tenendo in considerazione il tempo necessario per il mwwwcontext switch, il processo p2 non attende nulla, perché entra subito in esecuzione, p4 attende 2 millisecondi, perché entra in esecuzione subito dopo p2, quindi p3 attende 6 millisecondi e p1 ne attende 12. Il tempo medio d'attesa è pari a (0+2+6+12)/4= 5 millisecondi.

Si può dimostrare che questo algoritmo è ottimale, in quanto consente di ottenere sempre il valore più basso di tempo d'attesa medio. Sfortunatamente non è possibile applicarlo, in quanto non è possibile conoscere anticipatamente quanto durerà l'esecuzione del processo. Tuttavia si può provare a predirlo, in quanto è probabile che sia simile ai precedenti.

Una tecnica comunemente usata è quella di utilizzare la mwxgmedia mobile esponenziale: mwxw τ τ n + 1 = α α t n + ( 1 − − α α ) τ τ n {\displaystyle \tau _{n+1}=\alpha t_{n}+(1-\alpha )\tau _{n}} dove mwya τ τ n {\displaystyle \tau _{n}} è la stima dell'n-esima esecuzione del processo, mwyq τ τ n + 1 {\displaystyle \tau _{n+1}} la stima attuale e mwyg α α {\displaystyle \alpha } ∈mwyw [ 0 , 1 ] {\displaystyle [0,1]} è il peso che deve essere assegnato al passato del processo e in genere per mwza α α = 1 / 2 {\displaystyle \alpha =1/2} si ha una discreta approssimazione del comportamento del processo e un risultato accettabile.

L'algoritmo SRTF (mwzwShortest Remaining Time First) si differenzia per il fatto che, quando viene sottomesso un nuovo processo la cui durata è minore del tempo necessario al processo in esecuzione per portare a terminare la propria sessione, lo scheduler provvede ad effettuare un mw0acontext switch e assegna l'uso della CPU al nuovo processo (prelazione - algoritmo preemptive). Il vantaggio è una gestione ottimale del tempo di attesa medio, in quanto processi dalla durata di esecuzione ridotta vengono eseguiti molto velocemente. Tra gli svantaggi potenziali, come avviene per l'SRT, vi è il fenomeno della mw0gstarvation dei processi in quanto processi con tempi di esecuzione rimanenti lunghi potrebbero rimanere in attesa indefinitamente nel caso venissero continuamente aggiunti processi di durata rimanente inferiore.

L'algoritmo HRRN (mw1qHigher Responsive Ratio Next) viene utilizzato per prevenire l'aging, ossia l'attesa eccessiva dei processi molto lunghi scavalcati da quelli più corti tramite SNPF e SRTF e si basa sul tempo di attesa di un processo utilizzando la formula mw1g R a t i o = ( W + S ) / S {\displaystyle Ratio=(W+S)/S} dove mw1w W {\displaystyle W} è il tempo di attesa e mw2a S {\displaystyle S} il prossimo CPU-burst (consumo della mw2qCPU) stimato.

Non potendo stimare con precisione il tempo di esecuzione di un processo nel momento in cui entrerà nel sistema, vi è la possibilità di stimare il tempo trascorso. Viene introdotto il concetto di retroazione secondo il quale si penalizzano i processi che hanno speso più tempo nel sistema. Lo mw3ascheduling a retroazione multilivello (o retroazione con code multiple, in inglese mw3qmultilevel feedback queue) è uno mw3gscheduling basato su quanti di tempo ed utilizza un meccanismo di priorità dinamica. Quando un processo entra nel sistema gli viene assegnata una priorità secondo criteri prefissati e viene inserito in una coda con un quanto di tempo fissato. Se il processo che si trova in stato mw3wrunning finisce il suo quanto di tempo, viene spostato in una coda con un quanto di tempo più grande ma con una priorità minore.

Ogni coda è gestita attraverso l'algoritmo di mw4qround-robin, tutte tranne l'ultima che è servita tramite FCFS. In questo modo:

• si favoriscono i processi più corti;

• con alcuni accorgimenti è possibile evitare condizioni di mw5qstarvation.

L'algoritmo FSS (mw6aFair share scheduling) raccoglie i processi in gruppi, così è possibile avere un controllo sulla distribuzione delle risorse computazionali più ampio.

Nell'ambito delle mw6wreti di telecomunicazioni in maniera molto simile al contesto informatico il termine "mw7ascheduling" indica il processo, messo in atto dallo scheduler in uscita ad un mw7qnodo di mw7gcommutazione a pacchetto, per selezionare e assegnare secondo varie possibili classi di priorità il diritto di mw7wtrasmissione alle varie possibili code (mw8abuffer) di mw8qpacchetti in situazione di mw8gcongestione garantendo il rispetto dei parametri di mw8wqualità di servizio (QoS) da offrire all'utente per le varie tipologie di traffico in ingresso.

• mw9wSistemi operativi, concetti ed esempi (A. Silbershatz, P. Baer Galvin, G. Gagne, 2003, editore Pearson Educational, ISBN 8871921402). Sistemi operativi, Gestione dei processi, gestione della memoria, I/O.

• mw-wArchitettura dei Sistemi di Elaborazione, volume 1 (F. Baiardi, A. Tomasi e Marco Vanneschi, 1988, mw-aFranco Angeli Edizioni, ISBN 882042746X). Fondamenti, firmware, architetture parallele.

• mw-wArchitettura dei Sistemi di Elaborazione, volume 2 (F. Baiardi, A. Tomasi, Marco Vanneschi, 1987, Franco Angeli Edizioni, ISBN 882042746X) Sistemi operativi, multiprocessore e distribuiti.

• mwaqqDeadlock

• mwaqyIterazione

• mwaqgKernel

• mwaqoKernel Linux

• mwaqwGNU Hurd

• mwaq4Starvation

• mwaraStochastic Fairness Queueing

• mwariTime-sharing

• mwarqWeighted fair queueing

• mwaryCiclo di fetch-execute

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «scheduler»

• citerefvocabolario-treccaniScheduler, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.

• citerefbritannica-com(EN) scheduling program, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

• citerefgarzanti-schedulerScheduler, in Grande Dizionario di Italiano, Garzanti Linguistica.